package experiment6;

import java.util.ArrayList;
import java.util.List;

/**
 * @author mazouri
 * @create 2021-12-02 10:48
 * <p>
 * 有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
 * 1≤n≤100  1≤wi，vi≤100  1≤W≤10000
 * <p>
 * 输入:
 * n=4
 * (w,v)={(2,3),(1,2),(3,4),(2,2)}
 * W=5
 * <p>
 * 输出:
 * 7（选择第0，1，3号物品）
 */
public class DpKnapsack {
    static int w = 5;
    static int[] weight = {2, 1, 3, 2};
    static int[] value = {12, 10, 20, 15};
    static int[][] dp = new int[weight.length + 1][w + 1];

    public static void main(String[] args) {
        System.out.println("最大价值为:" + dp());
        System.out.println("构成最大价值的物品编号：" + find());
    }


    /**
     * 动态规划 查找最大价值
     * @return 最大值
     */
    private static int dp() {
        for (int i = 1; i <= weight.length; i++) {
            for (int j = 1; j <= w; j++) {
                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                if (j < weight[i - 1]) dp[i][j] = dp[i - 1][j];
                    //dp[i - 1][j - weight[i]] + value[i] 当前物品的价格+剩余空间的价值
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            }
        }

        return dp[weight.length][w];
    }

    /**
     * @return 最大值具体由哪些物品构成
     */
    private static List<Integer> find() {
        //具体物品编号
        ArrayList<Integer> res = new ArrayList<>();
        //反推出结果
        for (int i = weight.length; i > 0; i--) {
            //如果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
            if (dp[i][w] > dp[i - 1][w]) {
                res.add(i);
                //当前的最大价值就是由dp[i-1][j-weight[i-1]]+value[i-1]构成
                w = w - weight[i - 1];
            }
        }
        return res;
    }
}
